/*
 * @lc app=leetcode id=474 lang=cpp
 *
 * [474] Ones and Zeroes
 */

// @lc code=start
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int dp[601][101][101];
        memset(dp, 0, sizeof(dp));
         int k=strs.size();
        vector<pair<int,int>> v(k,{0,0});
        for(int i=0;i<k;i++){
            for(int j=0;j<strs[i].size();j++){
                if(strs[i][j]=='0') v[i].first++;
                else v[i].second++;
            }
        }
        for (int k = 1; k <= v.size(); ++k) {
            auto p = v[k-1];
            for (int i = 0; i <= m; ++i) {
                for (int j = 0; j <= n; ++j) {
                    if (p.first <= i && p.second <= j) {
                        dp[k][i][j] = max(dp[k-1][i-p.first][j-p.second] + 1, dp[k-1][i][j]);
                    } else {
                        dp[k][i][j] = dp[k-1][i][j];
                    }

                }
            }
        }
        int ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans = std::max(ans, dp[strs.size()][i][n]);
        }
        return ans;
    }
};
// @lc code=end

